package leetcode.code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * 给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
 *
 * 提示：
 *
 * 整数点是具有整数坐标的点。
 * 矩形周边上的点包含在矩形覆盖的空间中。
 * 第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中 [x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
 * 每个矩形的长度和宽度不超过 2000。
 * 1 <= rects.length <= 100
 * pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。
 * pick 最多被调用10000次。
 *  
 *
 * 示例 1：
 *
 * 输入:
 * ["Solution","pick","pick","pick"]
 * [[[[1,1,5,5]]],[],[],[]]
 * 输出:
 * [null,[4,1],[4,1],[3,3]]
 * 示例 2：
 *
 * 输入:
 * ["Solution","pick","pick","pick","pick","pick"]
 * [[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
 * 输出:
 * [null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
 *  
 *
 * 输入语法的说明：
 *
 * 输入是两个列表：调用的子例程及其参数。Solution 的构造函数有一个参数，即矩形数组 rects。pick 没有参数。参数总是用列表包装的，即使没有也是如此。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/random-point-in-non-overlapping-rectangles
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 非重叠矩形中的随机点 {

    static class Solution {

        private int[] area;
        private int sumArea;
        private int[][] rects;

        public Solution(int[][] rects) {
            this.rects = rects;
            area = new int[rects.length];
            for (int i = 0; i < rects.length; i++){
                if (rects[i].length == 4){
                    area[i] = (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
                    sumArea += area[i];
                }
            }
        }

        public int[] pick() {
            int r = new Random().nextInt(sumArea);
            r += 1;
            int j = 0;
            for (int i : area){
                if (r <= i){
                    break;
                }else {
                    r -= i;
                }
                j++;
            }
            // 先 x 后 y
            int width = rects[j][2] - rects[j][0] + 1;
            int x = r % width;
            int y = x==0 ? r/width-1 : r/width;
            return new int[]{rects[j][0]+x, rects[j][1]+y};
        }
    }

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(rects);
 * int[] param_1 = obj.pick();
 */

    public static void main(String[] args){
        Solution s = new Solution(new int[][]{{-2,-2,-1,-1},{1,0,3,0}});
        System.out.println(Arrays.toString(s.pick()));
        System.out.println(Arrays.toString(s.pick()));
        System.out.println(Arrays.toString(s.pick()));
        System.out.println(Arrays.toString(s.pick()));
    }
}
